package com.algrithom.graph.hasdirection;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;
import java.util.Optional;

import com.common.model.Vertex;

/**
 * 邻接表
 *
 * @author think
 */
public class AdjacencyList {
    
    /**
     * 节点链表list，该list的每一项又是一个ArrayList,即每个节点相当于一个二维数组
     */
    private final List<Vertex> nodeList = new ArrayList<>();
    
    public AdjacencyList(){}
    
    public static void main(String[] args){
        // 初始化一个顶点数为5的链表集合
        AdjacencyList adjacencyList = new AdjacencyList();

        // 给链表添加边
        // A --> B
        Vertex headNode = Vertex.builder().name(String.valueOf(0)).build();
        Vertex node = Vertex.builder().name(String.valueOf(1)).build();
        adjacencyList.addEdges(headNode,node);
        // A --> D
        headNode = Vertex.builder().name(String.valueOf(0)).build();
        node = Vertex.builder().name(String.valueOf(3)).build();
        adjacencyList.addEdges(headNode,node);
        // A --> E
        headNode = Vertex.builder().name(String.valueOf(0)).build();
        node = Vertex.builder().name(String.valueOf(4)).build();
        adjacencyList.addEdges(headNode,node);
        // B --> 1
        headNode = Vertex.builder().name(String.valueOf(1)).build();
        node = Vertex.builder().name(String.valueOf(0)).build();
        adjacencyList.addEdges(headNode,node);
        // B --> C
        headNode = Vertex.builder().name(String.valueOf(1)).build();
        node = Vertex.builder().name(String.valueOf(2)).build();
        adjacencyList.addEdges(headNode,node);
        // B --> E
        headNode = Vertex.builder().name(String.valueOf(1)).build();
        node = Vertex.builder().name(String.valueOf(3)).build();
        adjacencyList.addEdges(headNode,node);
        // C --> B
        headNode = Vertex.builder().name(String.valueOf(2)).build();
        node = Vertex.builder().name(String.valueOf(1)).build();
        adjacencyList.addEdges(headNode,node);
        // C --> E
        headNode = Vertex.builder().name(String.valueOf(2)).build();
        node = Vertex.builder().name(String.valueOf(4)).build();
        adjacencyList.addEdges(headNode,node);
        // D --> A
        headNode = Vertex.builder().name(String.valueOf(3)).build();
        node = Vertex.builder().name(String.valueOf(0)).build();
        adjacencyList.addEdges(headNode,node);
        // D --> C
        headNode = Vertex.builder().name(String.valueOf(3)).build();
        node = Vertex.builder().name(String.valueOf(2)).build();
        adjacencyList.addEdges(headNode,node);
        // E --> A
        headNode = Vertex.builder().name(String.valueOf(4)).build();
        node = Vertex.builder().name(String.valueOf(0)).build();
        adjacencyList.addEdges(headNode,node);
        // E --> B
        headNode = Vertex.builder().name(String.valueOf(4)).build();
        node = Vertex.builder().name(String.valueOf(1)).build();
        adjacencyList.addEdges(headNode,node);

        // 输出链表图
        adjacencyList.nodeList.forEach(nd -> {
            adjacencyList.printNodeList(nd);
            System.out.println();
        });
    }
    
    /**
     * 为顶点编号分别为i和j的两个顶点添加边
     *
     * @param headNode 头结点
     * @param node 当前结点
     */
    public void addEdges(Vertex headNode,Vertex node){
        Optional<Vertex> head = nodeList.stream().filter(vertex -> headNode.getNumber() == vertex.getNumber()).findFirst();
        if (head.isPresent()) {
            insertNode(node,head.get());
        } else {
            insertNode(node,headNode);
            nodeList.add(headNode);
        }
    }
    
    private void insertNode(Vertex node,Vertex nd){
        while (Objects.nonNull(nd.getNextNode())) {
            nd = nd.getNextNode();
        }
        nd.setNextNode(node);
    }
    
    /**
     * 输出链表图
     */
    public void printNodeList(Vertex node){
        if (Objects.nonNull(node)) {
            if (Objects.isNull(node.getNextNode())) {
                System.out.print(node.getNumber());
            } else {
                System.out.print(node.getNumber() + "——>");
            }
            printNodeList(node.getNextNode());
        }
    }
}
